#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STTypeDate;
typedef struct Stack {
    int* a;
    int top;
    int capacity;
}ST;

void STInit(ST* pst) {
    assert(pst);
    //STTypeDate* newspace = (STTypeDate*)malloc(sizeof(STTypeDate) * 4);
    //if (newspace == NULL)
    //{
    //	perror("malloc");
    //}
    //pst->a = newspace;
    pst->a = NULL;
    pst->top = -1;
    pst->capacity = 0;
}
void STPush(ST* pst, STTypeDate x) {
    assert(pst);
    if (pst->top + 1 == pst->capacity)
    {
        int newcapacity = pst->capacity == NULL ? 4 : pst->capacity * 2;
        STTypeDate* tmp = (STTypeDate*)realloc(pst->a, sizeof(STTypeDate) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc:");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    ++(pst->top);
    pst->a[pst->top] = x;
}
void STPop(ST* pst) {
    assert(pst);
    assert(pst->top >= 0);
    pst->top--;
}
STTypeDate STTop(ST* pst) {
    assert(pst);
    assert(pst->top >= 0);
    return pst->a[pst->top];
}
int STSize(ST* pst) {
    assert(pst);
    return pst->top + 1;
}
int STEmpty(ST* pst) {
    assert(pst);
    if (pst->top == -1)
        return 1;
    else
        return 0;
}
void STDistory(ST* pst) {
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = -1;
    pst->capacity = 0;
}
void STInit(ST* pst);
void STPush(ST* pst, STTypeDate x);
void STPop(ST* pst);
STTypeDate STTop(ST* pst);
STTypeDate STSize(ST* pst);
int STEmpty(ST* pst);
void STDistory(ST* pst);


typedef struct {
    ST q1;
    ST q2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* newnode = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&newnode->q1);
    STInit(&newnode->q2);
    return newnode;
}

void myQueuePush(MyQueue* obj, int x) {
    if (!STEmpty(&obj->q1))
    {
        STPush
        (&obj->q1, x);
    }
    else {
        STPush(&obj->q2, x);
    }
}

int myQueuePop(MyQueue* obj) {
    ST* empty = &obj->q1;
    ST* noempty = &obj->q2;
    if (!STEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while (STSize(noempty) > 1)
    {
        STPush(empty, STTop(noempty));
        STPop(noempty);
    }
    int cur = STTop(noempty);
    STPop(noempty);
    while (STSize(empty) >= 1)
    {
        STPush(noempty, STTop(empty));
        STPop(empty);
    }
    return cur;
}

int myQueuePeek(MyQueue* obj) {
    ST* empty = &obj->q1;
    ST* noempty = &obj->q2;
    if (!STEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while (STSize(noempty) > 1)
    {
        STPush(empty, STTop(noempty));
        STPop(noempty);
    }
    int cur = STTop(noempty);
    STPush(empty, STTop(noempty));
    STPop(noempty);
    while (STSize(empty) >= 1)
    {
        STPush(noempty, STTop(empty));
        STPop(empty);
    }
    return cur;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->q1) && STEmpty(&obj->q2);
}

void myQueueFree(MyQueue* obj) {
    STDistory(&obj->q1);
    STDistory(&obj->q2);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/
int main()
{

}
